#include <iostream>
#include <vector>
using namespace std;
// 归并排序
void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    int tmp[right - left + 1] = {};
    int cur = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[cur++] = nums[i++];
        else
            tmp[cur++] = nums[j++];
    }
    if (i == mid + 1) {
        while (j <= right) tmp[cur++] = nums[j++];
    } else {
        while (i <= mid) tmp[cur++] = nums[i++];
    }
    for (int t = left; t <= right; t++) { nums[t] = tmp[t - left]; }
}
